1. Field of the Invention
The present invention relates to techniques for solving optimization problems within computer systems. More specifically, the present invention relates to a method and an apparatus that uses interval techniques to solve a multi-objective optimization problem.
2. Related Art
In many real-world optimization problems, there are often several objectives that one would like to optimize. In such cases, rarely do the optima of each objective coincide. Hence, one is left with tradeoffs between the individual objectives that must be incorporated in the solution. The goal of multi-objective optimization is then to determine a set of points that describe the optimal trade-offs between objectives.
An example of multi-objective optimization is that of minimizing price and maximizing performance. A common metric associated with these two objectives is the price-performance ratio. This number, however, oversimplifies the optimization problem. This oversimplification lies in the implicit assumption that a unit of price is equal to a unit of performance, which in general is not the case. For example, a college freshman and a national lab would most likely weight these two objectives differently when purchasing a computer. A more insightful approach to the problem is depicted in FIG. 1, which shows the price and runtime (inverse performance) of a set of points representing (fictitious) computers. Expressed in this manner, one would like to minimize each objective.
Unfortunately, minimizing both objectives simultaneously is generally not possible, and is not the case in this example. The best one can do is come up with an optimal trade-off, where it is not possible to improve one objective without degrading the other. The filled circles in FIG. 1 are points which exhibit this optimal trade-off, and comprise what is termed the “Pareto front.” Obtaining the Pareto front is one of the goals of multi-objective optimization, both in identifying optimal points and in providing a sensitivity analysis. This sensitivity analysis considers the shape of the Pareto front. Convex portions of the Pareto front (points which lie on the convex hull of all points) indicate an ability to satisfy all objectives relative to regions of the Pareto front which are nonconvex (the “indented” region of Pareto front in FIG. 1).
In addition to determining the Pareto front, another goal of multi-objective optimization is to identify values of the objective functions' independent variables which are mapped to points on the Pareto front. In our example, processor speed, memory, system architecture, etc., are all independent variables (perhaps constrained) of both price and performance objective functions. One would like to know which sets of these independent variables map to points on the Pareto front. Such sets are termed “Pareto optimal sets.”
While the application of intervals to solving the multi-objective optimization problem is new, there are a variety of methods for obtaining the Pareto front for analytical expressions. These methods include the weighted objective or aggregate function method, evolutionary algorithms (see “Zitzler, E., Deb, D., and L. Thiele (2000) “Comparison of Multiobjective Evolutionary Algorithms: Empirical Results,” Evolutionary Computing 8(2): 173-195), and adjoint-gradient methods (see Nemec, M. and D. W. Zingg (2001) “Towards Efficient Aerodynamic Shape Optimization Based on the Navier-Stokes Equations,” 15th AIAA Computational Fluid Dynamics Conference, AIAA 2001-2532). Each of these methods has its benefits and detractions. The aggregated function method turns the problem into a single objective optimization by weighting each objective. For example, if we have n objectives, {ƒ1, . . . , ƒn,}, we wish to simultaneously minimize, then one can minimize the fitness function
  F  =            ∑              i        =        1            n        ⁢                  ⁢                  w        i            ⁢                        f          i                ⁡                  (          x          )                    for all combinations of wi such that 0≦wi≦1 and
            ∑              i        =        1            n        ⁢                  ⁢          w      i        =  1.
Although simple in concept, there are several disadvantages to this method. The first is that uniform variations in the weightings space do not evenly map out the Pareto front. A second, and more substantial, disadvantage is that this method cannot capture nonconvex regions of the Pareto front. A third disadvantage is that the method does not guarantee finding all solutions. (Note that this disadvantage is to common to all existing solution methods.)
Hence, what is needed is a method and an apparatus for determining a Pareto front for a multi-objective optimization problem without the above-described problems.